A typical Internet Protocol (IP) network comprises a set of IP routers each having one or more ingress interface and one or more egress interfaces (typically, for duplex links, a single interface will act both as ingress and egress interface). Each interface is attached to a link which carries packets between routers. A link may be for example an Ethernet link, optical link, etc. Within a router, each ingress interface is part of a so-called line card. This line card connects the interface to the internal backplane of the node. Each line card has a memory storing a routing table sometimes referred to as forwarding table. A routing table stores for each destination IP address prefix an egress interface. When a packet is received at an ingress interface of a router, the corresponding line card uses its routing table to determine from the IP Address prefix the egress interface over which the packet should be sent. Conventionally, a routing table is computed by software running at an IP router, with the same table being provided to each line card of that router.
Failures of IP links within an IP network can be fairly common. A failure may result due to failure of a link itself, or due to failure of a node at the other end of a link. Various fault recovery procedures are in use to mitigate the effects of link failures. Typically, these rely upon a router detecting a failure in respect of a link to which the router is directly connected. The router then “floods” the change of link state as a protocol message to all its neighbours, which in turn also flood the link state update to all their neighbour until all network routers learn about the topology change. After learning the change of link state, either by direct detection or by being informed via a signaling message, each router re-computes its routing table to provide alternative routes (if available) which avoid the failed link. The re-computed table is passed to each line card at the router. Each IP router of the network re-computes its own routing table. Examples of such conventional protocols include Open Shortest Path First (OSPF) and Intermediate System-to-Intermediate System (IS-IS).
It takes a significant time for a fault detection at one IP router to propagate to other routers with a network and to effect the routing tables used by the line cards at those other routers due to link transmission delays and to the time taken to recompute the routing tables and store these in the link cards. Even though an individual router (e.g. the one that detects the failure) might update its routing table quickly, this will not be effective until other routers have similarly recomputed their routing tables. In the meantime, packets can be dropped and service levels reduced.
In an attempt to mitigate these problems, a new IP Fast Reroute (IPFRR) framework (see references [1] to [5] below) has been proposed. The object of IPFRR framework is to allow individual routers to quickly re-route packets onto pre-computed alternative paths after local detection of a link failure, and prior to sending out failure notifications to neighbouring nodes according, for example, to OSPF. Transient link errors are thus extremely short and most packets can reach their destination. In addition, network reconfiguration can be delayed until it is determined that the link failure is persistent.
One specific IPFRR procedure is described in reference [4] below. This is known as “Not-via Addresses”. This procedure provides 100% link fault recovery for at most one failed link. However, Not-via-Addresses requires tunneling and the provision of two IP addresses per interface. In the case of a densely connected network, the administration and management of tunneling interfaces and their addresses can be cumbersome.
A problem that should always be addressed in IP networks is loop formation. This results in packets being transferred around a loop without ever reaching their final destination. Loops occupy valuable network bandwidth and result in dropped packets. Another IPFRR procedure is known as Failure Insensitive Routing (FIR) (see reference [5]) and specifically aims to reduce the risk of loop creation after a local and fast-reroute, without having to rely on tunnels. Routing tables are provided at each router on a per line card basis. That is to say that the egress interface to which incoming packets are sent is determined not only by the destination (IP address), but also by the ingress interface on which the packet is received. Referring to FIG. 1, a seven router IP network is illustrated. Consider for example router B. A first routing table associated with the ingress interface attached to router S is configured to cause packets received at that interface and having an IP address routing prefix mapping to router D, to be forwarded to router D across the B-C link. However, a second routing table associated with the ingress interface to router C is configured to forward packets received at that interface and having the same routing prefix, to be forwarded to router D across the B-A link.
Referring again to FIG. 1, consider the case where router S sends a packet destined for router D. The solid arrows illustrate the optimal route, i.e. S→B→C→D. Now consider what happens when the link between C and D fails. Upon detection of this failure, router C will return packets received from router B, to router B. As these packets are received by router B at a different ingress interface from which they were received in the “outgoing” leg, despite the fact the destination IP address routing prefix is the same, router B will forward the packet over a different egress interface, namely the interface to router A. Thereafter, packets sent from S to D follow the path S→B→C→B→A→E→D (where the additional legs are illustrated by the dashed arrows in FIG. 1). Of course, at some point the OSPF (or other) protocol will cause the routing tables to be updated across the network, resulting in a new optimal route S→B→A→E→D. In the interim, however, no packets will be dropped.
Loop creation in FIR is still possible however. This is illustrated in FIG. 2. Consider that the C-D link has failed as described with respect to FIG. 1, and that packets are being sent between C and D along the S→B→C→B→A→E→D route. Consider further that the link between E and D now fails. Router E will begin returning packets to router A which will in turn route them to B. Router B will pass packets to C which will return them to B and so on.
Rerouting and loop-prevention techniques are also described in: WO 2006107875, WO 2006065439, WO 2006093642, WO 2006065440, US 20050063311, WO 2004019565, and U.S. Pat. No. 6,065,061.
It is noted that link failure and looping problems may arise in other, non-IP packet switched networks, for example in Ethernet networks.